Masala #0943

Xotira 64 MB Vaqt 1000 ms Qiyinchiligi 43 %
14

  

Logistika muammosi

Logistikada ham, kam emas hollarda muammolariga yechimni dasturlash va algoritmlar orqali topib berish mumkin. Quyidagi muammoga ham yechim topib ko`ring.

Bir mamlakatda \(N\) ta shahar va har bir shaharlarni o`zaro bog`lovchi bir tomonlama yo`llar mavjud. Har bir yo`l o`z kengligiga ega. Logistika firmasining yangi loyihasiga ko`ra, bu davlatda har bir shahardan barcha boshqa shaharlarga yuk mashinalari mahsulotga to`ldirilib jo`natiladi.

Muammo shundaki, sig`imi \(x\) miqdorli mahsulot olib o`tadigan yuk mashinasi, \(y\) kenglikdagi yo`ldan o`tishi uchun, \(x \leq y\) shart bajarilishi shart. Ammo firmaning ustaviga ko`ra barcha yuk mashinalarini bir xil sig`imda bo`lishi lozim.

Ushbu mamlakatda firma har bir shahardan boshqa ixtiyoriy shaharga yuk mashinasi orqali mahsulot olib o`ta olish sharti bilan yuk mashinalarining eng katta sig`imini toping.


Kiruvchi ma'lumotlar:

Yagona qatorda bitta butun son \(N(1 \leq N \leq 300)\) kiritiladi.

Keyingi \(n\) ta qatorning har birida \(N\) tadan natural son - o`lchami \(N\) bo`lgan butun sonlardan iborat kvadrat matritsa kiritiladi. Matritsadagi \(i\)-ustun, \(j\)-qatorda joylashgan son, \(i\)-shahardan \(j\)-shaharga boruvchi yo`lning kengligi kiritladi.


Chiquvchi ma'lumotlar:

Yagona qatorda bitta butun son ushba mamlakatda firma loyihasini o`tkazishi mumkin bo`lgan yuk mashinalarining eng katta sig`imini chiqaring.


Misollar
# input.txt output.txt
1
3
0 8 3
7 0 13
4 100 0
7
2
4
0 20 4 1
100 0 2 29
25 100 0 13
19 7 93 0
20
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin